package com.cjm.algorithm.leetcode;

import java.util.*;

public class TopKFrequent347 {
    public static int[] topKFrequent(int[] nums, int k) {
        // 使用字典，统计每个元素出现的次数，元素为键，元素出现的次数为值
        HashMap<Integer,Integer> map = new HashMap();
        for(int num : nums){
            if (map.containsKey(num)) {
                map.put(num, map.get(num) + 1);
            } else {
                map.put(num, 1);
            }
        }
        // 遍历map，用最小堆保存频率最大的k个元素
        PriorityQueue<TopKFrequentHelp> pq = new PriorityQueue<TopKFrequentHelp>(new Comparator<TopKFrequentHelp>() {
            @Override
            public int compare(TopKFrequentHelp o1, TopKFrequentHelp o2) {
                return o1.getCount() - o2.getCount();
            }
        });
        for (Integer key : map.keySet()) {
             if (pq.size() == k) {
                 TopKFrequentHelp remove = pq.poll();
                 if (remove.getCount() > map.get(key)) {
                     pq.add(remove);
                 } else {
                     TopKFrequentHelp temp = new TopKFrequentHelp();
                     temp.setNum(key);
                     temp.setCount(map.get(key));
                     pq.add(temp);
                 }
            } else {
                 TopKFrequentHelp temp = new TopKFrequentHelp();
                 temp.setNum(key);
                 temp.setCount(map.get(key));
                 pq.add(temp);
             }

        }
        // 取出最小堆中的元素
        int[] res = new int[pq.size()];
        int index = 0;
        while (!pq.isEmpty()) {
            res[index++] = pq.poll().getNum();
        }
        return res;
    }

    static class TopKFrequentHelp{
        private Integer num;
        private Integer count;

        public Integer getNum() {
            return num;
        }

        public void setNum(Integer num) {
            this.num = num;
        }

        public Integer getCount() {
            return count;
        }

        public void setCount(Integer count) {
            this.count = count;
        }
    }

    public static void main(String[] args) {
        topKFrequent(new int[]{4, 1, -1, 2, -1, 2, 3}, 2);
    }
}
